Three Heuristics for δ-Matching: δ-BM Algorithms
Identifieur interne : 00B372 ( Main/Exploration ); précédent : 00B371; suivant : 00B373Three Heuristics for δ-Matching: δ-BM Algorithms
Auteurs : Maxime Crochemore [France] ; Costas S. Iliopoulos [Royaume-Uni, Australie] ; Thierry Lecroq [France] ; Wojciech Plandowski [Pologne] ; Wojciech Rytter [Pologne, Royaume-Uni]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2002.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
- Algorithm, Alphabet, Approximate dictionaries, Approximate string, Average number, Best results, Computer science, Crochemore, Data processing, Data structure, Data structures, Distance, Equivalence classes, Exact string, Experimental results, Fast algorithm, Heuristic, Heuristic method, Initial state, Instytut informatyki, Large alphabets, Large shift, Large values, Larger values, Linear size equivalent, Maxime crochemore, Musical acoustics, Musical applications, Musical sequences, Naive algorithm, Node, Other words, Pattern matching, Pitch intervals, Random string, Rejection ratio, Rejection ratios, Same equivalence class, Small values, Smaller rejection ratio, String matching, Subword, Subword graph, Subword graphs, Such algorithms, Text character inspections, Time complexity, Trie, Type algorithms, Uniwersytet warszawski.
- Teeft :
- Algorithm, Alphabet, Approximate dictionaries, Approximate string, Average number, Best results, Computer science, Crochemore, Data structure, Data structures, Equivalence classes, Exact string, Experimental results, Heuristic, Initial state, Instytut informatyki, Large alphabets, Large shift, Large values, Larger values, Linear size equivalent, Maxime crochemore, Musical applications, Musical sequences, Naive algorithm, Node, Other words, Pitch intervals, Random string, Rejection ratio, Rejection ratios, Same equivalence class, Small values, Smaller rejection ratio, Subword, Subword graph, Subword graphs, Such algorithms, Text character inspections, Time complexity, Trie, Type algorithms, Uniwersytet warszawski.
Abstract
Abstract: We consider a version of pattern matching useful in processing large musical data: δ-matching, which consists in finding matches which are δ-approximate in the sense of the distance measured as maximum difference between symbols. The alphabet is an interval of integers, and the distance between two symbols a, b is measured as |a - b|. We present δ-matching algorithms fast on the average providing that the pattern is “non-flat”and the alphabet interval is large. The pattern is “flat” if its structure does not vary substantially. We also consider (δ,γ)-matching, where γ is a bound on the total number of errors. The algorithms, named δ-BM1, δ-BM2 and δ-BM3 can be thought as members of the generalized Boyer-Moore family of algorithms. The algorithms are fast on average. This is the first paper on the subject, previously only “occurrence heuristics” have been considered. Our heuristics are much stronger and refer to larger parts of texts (not only to single positions).
Url:
DOI: 10.1007/3-540-45452-7_16
Affiliations:
- Australie, France, Pologne, Royaume-Uni
- Angleterre, Grand Londres, Haute-Normandie, Région Normandie, Île-de-France
- Londres, Marne-la-Vallée, Rouen
- Université de Rouen
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000D02
- to stream Istex, to step Curation: 000D02
- to stream Istex, to step Checkpoint: 001C02
- to stream Main, to step Merge: 00C163
- to stream PascalFrancis, to step Corpus: 005403
- to stream PascalFrancis, to step Curation: 000D23
- to stream PascalFrancis, to step Checkpoint: 005159
- to stream Main, to step Merge: 00C280
- to stream Main, to step Curation: 00B372
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Three Heuristics for δ-Matching: δ-BM Algorithms</title><author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name></author><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></author><author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name></author><author><name sortKey="Plandowski, Wojciech" sort="Plandowski, Wojciech" uniqKey="Plandowski W" first="Wojciech" last="Plandowski">Wojciech Plandowski</name></author><author><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:45326914D9948901D8BC7A6B41EDC8551D60A2E6</idno><date when="2002" year="2002">2002</date><idno type="doi">10.1007/3-540-45452-7_16</idno><idno type="url">https://api.istex.fr/document/45326914D9948901D8BC7A6B41EDC8551D60A2E6/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000D02</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000D02</idno><idno type="wicri:Area/Istex/Curation">000D02</idno><idno type="wicri:Area/Istex/Checkpoint">001C02</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001C02</idno><idno type="wicri:doubleKey">0302-9743:2002:Crochemore M:three:heuristics:for</idno><idno type="wicri:Area/Main/Merge">00C163</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:03-0189280</idno><idno type="wicri:Area/PascalFrancis/Corpus">005403</idno><idno type="wicri:Area/PascalFrancis/Curation">000D23</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">005159</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">005159</idno><idno type="wicri:doubleKey">0302-9743:2002:Crochemore M:three:heuristics:for</idno><idno type="wicri:Area/Main/Merge">00C280</idno><idno type="wicri:Area/Main/Curation">00B372</idno><idno type="wicri:Area/Main/Exploration">00B372</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Three Heuristics for δ-Matching: δ-BM Algorithms</title><author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Institut Gaspard Monge, Université Marne-la-Vallée, Cité Descartes 5 Bd Descartes, Champs-Sur-Marne, 77454, Marne-la-Vallée Cedex 2</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Marne-la-Vallée</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Dept. of Computer Science, King’s College London, WC2R 2LS, London</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>School of Computing, Curtin University of Technology, GPO Box 1987 U, WA</wicri:regionArea><wicri:noRegion>WA</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>LIFAR-ABISS, Faculté des Sciences et Techniques, Université de Rouen, 76821, Mont-Saint-Aignan Cedex</wicri:regionArea><orgName type="university">Université de Rouen</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Plandowski, Wojciech" sort="Plandowski, Wojciech" uniqKey="Plandowski W" first="Wojciech" last="Plandowski">Wojciech Plandowski</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Instytut Informatyki, Uniwersytet Warszawski, ul. Banacha 2, 02-097, Warszawa</wicri:regionArea><wicri:noRegion>Warszawa</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Instytut Informatyki, Uniwersytet Warszawski, ul. Banacha 2, 02-097, Warszawa</wicri:regionArea><wicri:noRegion>Warszawa</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Department of Computer Science, Liverpool University, Peach Street, L69 7ZF, Liverpool</wicri:regionArea><wicri:noRegion>Liverpool</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2002</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Alphabet</term><term>Approximate dictionaries</term><term>Approximate string</term><term>Average number</term><term>Best results</term><term>Computer science</term><term>Crochemore</term><term>Data processing</term><term>Data structure</term><term>Data structures</term><term>Distance</term><term>Equivalence classes</term><term>Exact string</term><term>Experimental results</term><term>Fast algorithm</term><term>Heuristic</term><term>Heuristic method</term><term>Initial state</term><term>Instytut informatyki</term><term>Large alphabets</term><term>Large shift</term><term>Large values</term><term>Larger values</term><term>Linear size equivalent</term><term>Maxime crochemore</term><term>Musical acoustics</term><term>Musical applications</term><term>Musical sequences</term><term>Naive algorithm</term><term>Node</term><term>Other words</term><term>Pattern matching</term><term>Pitch intervals</term><term>Random string</term><term>Rejection ratio</term><term>Rejection ratios</term><term>Same equivalence class</term><term>Small values</term><term>Smaller rejection ratio</term><term>String matching</term><term>Subword</term><term>Subword graph</term><term>Subword graphs</term><term>Such algorithms</term><term>Text character inspections</term><term>Time complexity</term><term>Trie</term><term>Type algorithms</term><term>Uniwersytet warszawski</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>4375</term><term>Acoustique musicale</term><term>Algorithme</term><term>Algorithme rapide</term><term>Appariement chaîne</term><term>Concordance forme</term><term>Distance</term><term>Méthode heuristique</term><term>Traitement donnée</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Alphabet</term><term>Approximate dictionaries</term><term>Approximate string</term><term>Average number</term><term>Best results</term><term>Computer science</term><term>Crochemore</term><term>Data structure</term><term>Data structures</term><term>Equivalence classes</term><term>Exact string</term><term>Experimental results</term><term>Heuristic</term><term>Initial state</term><term>Instytut informatyki</term><term>Large alphabets</term><term>Large shift</term><term>Large values</term><term>Larger values</term><term>Linear size equivalent</term><term>Maxime crochemore</term><term>Musical applications</term><term>Musical sequences</term><term>Naive algorithm</term><term>Node</term><term>Other words</term><term>Pitch intervals</term><term>Random string</term><term>Rejection ratio</term><term>Rejection ratios</term><term>Same equivalence class</term><term>Small values</term><term>Smaller rejection ratio</term><term>Subword</term><term>Subword graph</term><term>Subword graphs</term><term>Such algorithms</term><term>Text character inspections</term><term>Time complexity</term><term>Trie</term><term>Type algorithms</term><term>Uniwersytet warszawski</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We consider a version of pattern matching useful in processing large musical data: δ-matching, which consists in finding matches which are δ-approximate in the sense of the distance measured as maximum difference between symbols. The alphabet is an interval of integers, and the distance between two symbols a, b is measured as |a - b|. We present δ-matching algorithms fast on the average providing that the pattern is “non-flat”and the alphabet interval is large. The pattern is “flat” if its structure does not vary substantially. We also consider (δ,γ)-matching, where γ is a bound on the total number of errors. The algorithms, named δ-BM1, δ-BM2 and δ-BM3 can be thought as members of the generalized Boyer-Moore family of algorithms. The algorithms are fast on average. This is the first paper on the subject, previously only “occurrence heuristics” have been considered. Our heuristics are much stronger and refer to larger parts of texts (not only to single positions).</div></front></TEI><affiliations><list><country><li>Australie</li><li>France</li><li>Pologne</li><li>Royaume-Uni</li></country><region><li>Angleterre</li><li>Grand Londres</li><li>Haute-Normandie</li><li>Région Normandie</li><li>Île-de-France</li></region><settlement><li>Londres</li><li>Marne-la-Vallée</li><li>Rouen</li></settlement><orgName><li>Université de Rouen</li></orgName></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name></region><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name></country><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></region><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name></country><country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></noRegion></country><country name="Pologne"><noRegion><name sortKey="Plandowski, Wojciech" sort="Plandowski, Wojciech" uniqKey="Plandowski W" first="Wojciech" last="Plandowski">Wojciech Plandowski</name></noRegion><name sortKey="Plandowski, Wojciech" sort="Plandowski, Wojciech" uniqKey="Plandowski W" first="Wojciech" last="Plandowski">Wojciech Plandowski</name><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B372 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B372 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:45326914D9948901D8BC7A6B41EDC8551D60A2E6
|texte= Three Heuristics for δ-Matching: δ-BM Algorithms
}}
| This area was generated with Dilib version V0.6.33. |  |